1582. Стрельба из лазера

Лазерная пушка расположена в точке (0, 0) на плоскости. Целями являются вертикальные отрезки с координатами концов (x[i], y1[i]) – (x[i], y2[i]). Выбирается произвольный угол от -π / 2 до π / 2 и производится выстрел. Выстрел под углом -π / 2 производится вертикально вниз, 0 – горизонтально вправо, π / 2 – вертикально вверх. Выстрелом является бесконечный луч, исходящий из начала координат. Выстрел попадает в цель, если луч и отрезок цели имеют общую точку.

Вычислить ожидаемое количество целей, которое может быть поражено одним выстрелом. Попадание в цель не меняет движение луча.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество целей n (1 ≤ n ≤ 50). Следующие три строки задают координаты целей. i-ое число второй строки каждого теста содержит значение x_i, i-ое число третьей строки - значение y1_i, i-ое число четвертой строки каждого теста - значение y2_i. Известно, что все координаты целые, значения x_i разные, 1 ≤ x_i ≤ 1000, -1000 ≤ y1_i, y2_i ≤ 1000.

Выход. Для каждого теста в отдельной строке вывести с 4 цифрами после десятичной точки ожидаемое количество целей, которое может быть поражено одним выстрелом.

Пример входа

1

1

-1

1

4

134 298 151 942

-753 -76 19 568

440 689 -39 672

Пример выхода

0.5000

1.4442

РЕШЕНИЕ

вероятность

Анализ алгоритма

Математическое ожидание суммы случайных величин равно сумме математических ожиданий этих величин. Поэтому достаточно вычислить для каждой цели вероятность ее поражения и просуммировать полученные значения.

Обозначим через a₁ и a₂ углы, при которых поражаются концы i - ой цели. Поскольку значения элементов массива x положительны, то a₁ = arctg(y1_i / x_i), a₂ = arctg(y2_i / x_i). i - ая цель поражается, если угол выстрела лежит между min(a₁, a₂) и max(a₁, a₂). Вероятность попадания в i - ую цель равна вероятности того, что точка, выбранная из отрезка [-π / 2, π / 2], попадет в отрезок [min(a₁, a₂) и max(a₁, a₂)]. Она равна (max(a₁, a₂) – min(a₁, a₂)) / π.

Реализация алгоритма

Объявим массивы, которые будут содержать координаты концов целей.

int x[51], yy1[51], yy2[51];

Функция numberOfHits возвращает искомое ожидаемое количество целей, которое может быть поражено одним выстрелом.

double numberOfHits(void)

{

double a1, a2, res = 0.0;

int i;

for(i = 0; i < n; i++)

{

a1 = atan(1.0 * yy1[i] / x[i]);

a2 = atan(1.0 * yy2[i] / x[i]);

res += fabs(a1 - a2) / PI;

}

return res;

}

Основная часть программы.

while(scanf("%d",&n) == 1)

{

for(i = 0 ;i < n; i++) scanf("%d",&x[i]);

for(i = 0 ;i < n; i++) scanf("%d",&yy1[i]);

for(i = 0 ;i < n; i++) scanf("%d",&yy2[i]);

res = numberOfHits();

printf("%.4lf\n",res);

}